#include <bits/stdc++.h>
using namespace std;
vector<int> val(100001);
vector<vector<int>> G(100001);
vector<int> dp(100001, 0);

bool is_Sqrt(int a, int b)
{
	int x = sqrt(a * b);
	return x * x == a * b;
}

int dfs(int root, int fa)
{
	if (dp[root] > 0)
	{
		return dp[root];
	}

	int not_Select_Root = 0;
	for (auto &child : G[root])
	{
		if (child != fa)
		{
			not_Select_Root += dfs(child, root);
		}
	}

	int select_Root = 0;
	for (auto &son : G[root])
	{
		if (son != fa && is_Sqrt(val[root], val[son]))
		{
			int tmp = 2;
			for (auto &grandson : G[son])
			{
				if (grandson != root)
				{
					tmp += dfs(grandson, son);
				}
			}
			select_Root = max(select_Root, not_Select_Root - dfs(son, root) + tmp);
		}
	}

	dp[root] = max(select_Root, not_Select_Root);
	return dp[root];
}

int main()
{
	ios::sync_with_stdio(false); // 关闭IO同步
	cin.tie(nullptr), cout.tie(nullptr);

	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> val[i];
	}

	int root = 0;
	for (int i = 0; i < n - 1; i++)
	{
		int a, b;
		cin >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
		if (root == 0)
		{
			root = a;
		}
	}

	cout << dfs(root, -1) << endl;

	return 0;
}
// 64 位输出请用 printf("%lld")